package com.cuijq.datasource;

import lombok.Data;

public class LinkDemo {

  public static void main(String[] args) {
    LinkDemo linkDemo = new LinkDemo();
    SingleChain singleChain = linkDemo.new SingleChain(5);
    singleChain.printChain(singleChain.getHead());

    System.out.println();
    Node node = singleChain.reverseList(singleChain.getHead());
    singleChain.printChain(node);
  }
  //1.理解指针与引用    存储内存对象的地址  将某个变量赋值给指针，将存储变量的地址赋值给指针，
  //指针中存储了这个变量的内存地址
  //  p->next=q。这行代码是说，p 结点中的 next 指针存储了 q 结点的内存地址
  //  p->next=p->next->next。这行代码表示，p 结点的 next 指针存储了 p 结点的下下一个结点的内存地址
  //2. 警惕指针丢失和内存泄漏 ,插入结点时，一定要注意操作的顺序
  //3. 利用哨兵简化实现难度

  //链表的检验，边界条件。
//    如果链表为空时，代码是否能正常工作？
//    如果链表只包含一个结点时，代码是否能正常工作？
//    如果链表只包含两个结点时，代码是否能正常工作？
//    代码逻辑在处理头结点和尾结点的时候，是否能正常工作？

  //1.单链表反转

  //2.链表中环的检测
  //3.两个有序的链表合并
  //4.删除链表倒数第 n 个结点
  //5.求链表的中间结点


  class SingleChain {

    private Node head;

    public SingleChain(int size) {
      head = new Node(0);
      Node cur = head;
      for (int i = 1; i < size; i++) {
        Node tmp = new Node(i);
        cur.setNext(tmp);
        cur = tmp;
      }
    }

    public Node getHead() {
      return head;
    }

    public void setHead(Node head) {
      this.head = head;
    }

    public void printChain(Node head) {
      Node h = head;
      while (null != h) {
        if (h.getNext()==null){
          System.out.print(h.getData() + "");
        }else {
          System.out.print(h.getData() + "->");
        }
        h = h.getNext();
      }
    }

    /**
     * 遍历发
     *
     * @param head
     * @return
     */
    public Node reverseIteratively(Node head) {
      Node pre = null;
      Node next = null;
      while (head != null) {
        next = head.next;
        head.next = pre;
        pre = head;
        head = next;
      }
      return pre;
    }

    public Node reverseList(Node head) {
      if (head == null) {
        return head;
      }
      Node pre = head;// 上一结点
      Node cur = head.getNext();// 当前结点
      Node tmp;// 临时结点，用于保存当前结点的指针域（即下一结点）
      while (cur != null) {// 当前结点为null，说明位于尾结点
        tmp = cur.getNext();
        cur.setNext(pre);// 反转指针域的指向

        // 指针往下移动
        pre = cur;
        cur = tmp;
      }
      // 最后将原链表的头节点的指针域置为null，还回新链表的头结点，即原链表的尾结点
      head.setNext(null);
      return pre;
    }

  }

  @Data
  class Node {

    private int data;// 数据域
    private Node next;// 指针域

    public Node(int data) {
      this.data = data;
    }
  }
}
